В клетки таблицы $$$n \times n$$$ необходимо расставить числа от 1 до $$$n^2$$$, каждое по одному разу. Расстановка тем лучше, чем меньше в ней плохих пар соседних клеток. Соседними считаются клетки, имеющие общую сторону. Пара соседних клеток считается плохой, если числа в этих клетках не являются взаимно простыми. Два числа называются взаимно простыми, если их наибольший общий делитель равен $$$1$$$.
Составьте таблицу с наименьшим количеством плохих пар клеток.
В первой строке задается количество наборов входных данных $$$T$$$. В этой задаче $$$T$$$ всегда равно 1.
В следующих $$$T$$$ строках содержатся описания входных данных. Каждое описание состоит из одного целого числа $$$n$$$ $$$(2 \le n \le 100)$$$ — размера таблицы.
Для каждого набора входных данных выведите $$$n$$$ строк, в каждой из которых должно быть по $$$n$$$ целых чисел — выбранная таблица.
Все числа от $$$1$$$ до $$$n^2$$$ должны встретиться в таблице ровно один раз.
Оценка за эту задачу — 60 баллов.
В этой задаче 60 тестов, и каждый тест оценивается максимум в 1 балл. Оценка за тест вычисляется как средняя оценка по наборам входных данных в тесте. В этой задаче оценка за тест равна оценке за единственный набор входных данных соответственно. Оценка за набор входных данных вычисляется по формуле:
$$$$$$grade = 1 - 1.7\cdot \frac{bad}{n^2}$$$$$$
где $$$bad$$$ и $$$n$$$ — количество плохих пар и размер таблицы соответственно.
1 2
1 4 2 3